package binarySearch;

import graph.numIslands;

public class search {
    public int search(int[] nums, int target) {
        if (nums[0]<nums[nums.length-1]) {
            int rs = binarySearch(nums, target,0,nums.length-1);
            return rs;
        }
        //乱序，先找min
        int left=0,right=nums.length-1,mid=0;
        while (left<right) {
            mid=(left+right)/2;
            if (nums[mid]<nums[right]) {
                right=mid;
            }else{
                left=mid+1;
            }
        }
        //判断区间
        mid=left;
        if (target<nums[mid]) {
            return -1;
        }else if(target>=nums[mid]&&target<=nums[nums.length-1]){
            int rs = binarySearch(nums, target,mid,nums.length-1);
            return rs;
        }else{
            int rs = binarySearch(nums, target,0,mid-1);
            return rs;
        }
    }
    public int binarySearch(int[] nums,int target,int left,int right){
        
        int mid=0;
        while (left<=right) {
            mid=(left+right)/2;
            if (nums[mid]==target) {
                return mid;
            }else if(nums[mid]>target){
                right=mid-1;
            }else{
                left=mid+1;
            }
        }
        return -1;
    }
    public static void main(String[] args) {
        search obj = new search();
        // int[] nums = new int[]{4,5,6,7,0,1,2};
        int[] nums = new int[]{4,1};
        // int[] nums = new int[]{4};
        System.out.println(obj.search(nums, 1));
    }
}
